<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>JS与链表及其各种方法</title>
</head>
<body>
<script>
var linkt = new LinkedList();
linkt.append(1);
linkt.append(2);
linkt.append(3);
    //首先创建一个单链表的构造函数

    function LinkedList() {
        //创建一种数据结构，用作保存链表中的数据，这种数据结构有两个属性，一个用于保存里面的值element一个用于指向下一个元
        //素的指针
        var Node = function (element) {
            //值保存为element
            this.element = element;
            //初始化其指向下一个元素的指针为null
            this.next = null;
        };
        //初始化链表长度,以及表头
        var length = 0,
            head = null;
        /*接下来我们要给链表实现一些方法
         *是否为空链表
         * 位置p是否是链表的最后一个位置
         * 找到链表中的某一个元素的位置
         * 在链表中的某一个位置插入一个元素，分为前插以及后插
         * 删除链表中某一个位置的元素
         * 删除某一个具体的元素
         * 删除链表
         * 返回链表元素的个数等等
         */
        this.append = function (element) {
            var node = new Node(element);　　　　　　　　//构造新的元素节点
            var current;
            if (head === null) {　　　　　　　　　　　　　//头节点为空时  当前结点作为头节点
                head = node;
            } else {
                current = head;
                while (current.next) {　　　　　　　　　　//遍历，直到节点的next为null时停止循环，当前节点为尾节点
                    current = current.next;
                }
                current.next = node;　　　　　　　　　　　　//将尾节点指向新的元素，新元素作为尾节点
            }
            length++;　　　　　　　　　　　　　　　　　　　　//更新链表长度
        };
        this.isEmpty = function () {
            //链表长度为零，即为空链表
            return length === 0;
        };
        this.isLastPos = function (p) {
            //判断p指向的下一个元素是否为空
            return p.next === null;
        };
        this.indexOf = function (element) {
            var current = head,
                index = 0;
            //循环链表查看是否有element
            while(current){
                if(element === current.element){
                    return index;
                }
                index++;
                current = current.next;
            }
            return -1;
        };
        this.insert = function (element, p) {
            var node = new Node(element),
                current = head,
                previous,
                index = 0;
            //判断给定的位置p是否合理，有没有超出链表范围
            if(p >= 0 && p <= length){
                if(p === 0){
                    //让之前的表头变成插入的结点的下一个结点
                    node.next = current;
                    //再让插入的结点成为表头
                    head = node;
                }else{
                    while(index++ < p){
                        previous = current;
                        current = current.next;
                    }
                    //属于前插，插入的元素排列在p 位置之前
                    previous.next = node;
                    node.next = current;
                    /*后插可以将while的判断条件改为index++ < p， 被插入的元素会排列在p 位置之后,前插可以将
                    * 条件改为index++ < p-1
                    */
                }
                length++;
                return true;
            }else{
                return false;//插入失败
            }
        };
        this.removeAt = function (p){
            //检查p是否越界
            if(p >= 0 && p <= length){
                var current = head,
                    previous,
                    index = 0;
                if(p === 0){
                    //相当于删除head，然后将当前的head的下一位变成head
                    head = current.next;
                }else{
                    while(index++ < p){
                        previous = current;
                        current.next = current;
                    }
                    //出来之后的结果，current所在的位置就是p，previous所在的位置是p的上一位
                    //直接让p的上一位的next指向p的next，直接舍弃p,顺便将p存储在current中
                    previous.next = current.next;
                }
                //记住在删除结束之后，将链表长度减1
                length--;
                return current.element;

            }else{
                return false;
            }
        };
        this.remove = function (element) {
            var index = this.indexOf(element);
            return this.removeAt(index);
        };
        this.sizeOf = function () {
            return length;
        };
        this.getHead = function () {
            return head;
        };
        this.toString = function () {
            var current = head,
                string = "";
            while(current){
                string += current.element + (current.next ? "," : " ");
                current = current.next;
            }
            return string;
        };
        this.print = function () {
            console.log(this.toString());
        }
}
    //创建一个双链表的构造函数
    function DoubleLinkedList() {
        //双链表只需要再附加一个域，指向上一个单元即可
        var Node = function (element) {
            this.element = element;
            //将节点单元前后的值都初始化为Null
            this.next = null;
            this.prev = null;
        };
        //将双链表初始化为头尾都为null,长度为0
        var length = 0;
        var head = null;
        var tail = null;
        /* 需要给双链表添加的方法
         * append(element): 添加元素到双向链表尾部
         * insert(position,element): 向双向链表中某个位置插入元素
         * removeAt(position): 移除双向链表中某个位置的元素
         * showHead(): 获取双向链表的头部
         * showLength(): 获取双向链表长度
         * showTail(): 获取双向链表尾部
         */
        this.append = function (element) {
            var node = new Node(element);
            //如果是空链表，就使head和tail等于node
            if(head === null){
                head = node;
                tail = node;
            }else{
                //非空链表
               var current = head;
               while(current.next){
                   current = current.next;
               }
               //此时current就是tail
               current.next = node;
               node.prev = current;
               tail = node;
            }
            length++;
        };
        this.insert = function (element, position) {
            var node = new Node(element),
                current = head,
                index = 0,
                previous;
            //判断输入的位置是否合理
            if(position >= 0 && position <= length){
                //如果在头部插入
                if(position === 0){
                    //判断是否是空链表
                    if(head === null){
                        head = node;
                        tail = node;
                    }else{
                        //不是空链表时
                        current.prev = node;
                        node.next = current;
                        head = node;
                    }
                //如果在尾部插入
                }else if(position === length){
                    current = tail;
                    current.next = node;
                    node.prev = current;
                    tail = node;
                //如果在中间插入
                }else{
                    //如果想插在position之前，写成index++ < position-1
                    //如果是插在后边，x
                    while(index++ < position){
                        previous = current;
                        current = current.next;
                    }//输出的previous对应position 前一位的单元，current等于position
                    previous.next = node;
                    node.next = current;

                    current.prev = node;
                    node.prev = previous;
                    //谨记prev 和 next 都要断掉并重新建立链接
                }
                length++;//给链表增加长度
                return true;
            }else{
                return false;
            }
        };
        this.removeAt = function (position) {
            var current = head,
                previous,
                index = 0;
                if(position > -1 && position < length){
                    if(position === 0){
                        //删除第一项，考虑了两种情况，链表中只有一项以及一项以上
                        head = current.next;
                        //将当前head的next赋予head
                        if(length === 1){
                            tail = null;
                        }else{
                            head.prev = null;
                        }
                    }else if(position === length - 1){
                        //删除最后一项
                        current = tail;
                        tail = current.prev;
                        tail.next = null;
                    }else{
                        while(index++ < position){
                            previous = current;
                            current = current.next;
                        }
                        //输出的previous对应position的上一位，current就在position上
                        previous.next = current.next;
                        current.next.prev = previous;//记得恢复prev的值
                    }
                    length--;
                    return current.element;
                }else{
                    return false;
              }
        };
        this.showHead = function () {
            return head;
        };
        this.showLength = function () {
            return length;
        };
        this.showTail = function () {
            return tail;
        };
        this.toString = function () {
            var current = head,
                string = "";
            while(current){
                string += current.element + (current.next ? "," : " ");
                current = current.next;
            }
            return string;
        };
        this.inverseToString = function () {
            var current = tail,
                s = current ? current.element : '';
            while(current && current.prev){
                current = current.prev;
                s += ', ' + current.element;
            }
            return s;
        };
        this.print = function () {
            console.log(this.toString());
        };
        this.length = function () {
            return length;
        }
        this.isEmpty = function () {
            return length === 0;
        };
        this.indexOf = function (element) {
            var current = head,
                index = 0;
            while(current){
                if(element === current.element){
                    return index;
                }
                index++;
                current = current.next;
            }
            return -1;//表示该链表中没有这样的元素
        }
        this.remove = function (element) {
            var index = this.indexOf(element);
            return this.removeAt(index);
        }
    }
</script>
</body>
</html>
